import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/23 10:05
 * @description DFS超时，每次深度找一种结果，容易超时
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {{0,0,0},{1,1,0},{1,1,0}};
        System.out.println(solution.shortestPathBinaryMatrix(grid));
    }

    private int[][] dirs = {{1, 1}, {1, 0}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
    private int value = Integer.MAX_VALUE;
    private int n;
    private boolean[][] visited;
    public int shortestPathBinaryMatrix(int[][] grid) {
        n = grid.length;
        visited = new boolean[n][n];
        dfs(grid, 0, 0, 1);
        return value;
    }

    public void dfs(int[][] grid, int i, int j, int count) {
        if (i == n - 1 && j == n - 1) {
            value = Math.min(value, count);
            return;
        }
        visited[i][j] = true;
        for (int k = 0; k < 8; k++) {
            int ni = i + dirs[k][0], nj = j + dirs[k][1];
            if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] == 0 && !visited[ni][nj]) {
                count++;
                visited[ni][nj] = true;
                dfs(grid, ni, nj, count);
                count--;
                visited[ni][nj] = false;
            }
        }
    }
}
